package com.techyuan.algorithm.sorts;

/**
 * 归并排序 时间复杂度:Θ(nlgn)
 * Created by tianjuntao on 2016/9/11.
 */
public class MegerSort implements ISort {
    public int[] sort(int[] sortingArr) {
        megerSort(sortingArr, 0, sortingArr.length - 1);
        return sortingArr;
    }

    private void megerSort(int[] arr, int p, int r) {
        if (p < r) {
            int q = (r + p) / 2;
            megerSort(arr, p, q);
            megerSort(arr, q + 1, r);
            meger(arr, p, q, r);
        }
    }

    private void meger(int[] arr, int p, int q, int r) {
        int n1 = q - p + 1;
        int n2 = r - q;
        Integer[] lArr = new Integer[n1 + 1];
        System.arraycopy(arr, p, lArr, 0, n1);
        Integer[] rArr = new Integer[n2 + 1];
        System.arraycopy(arr, q + 1, rArr, 0, n2);
        lArr[n1] = Integer.MAX_VALUE;
        rArr[n2] = Integer.MAX_VALUE;

        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (lArr[i] <= rArr[j]) {
                arr[k] = lArr[i];
                i++;
            } else {
                arr[k] = rArr[j];
                j++;
            }
        }
    }
}
